import math
from .priority_queue_base import PriorityQueueBase


class MaxHeapPriorityQueue(PriorityQueueBase):
    """
    A max-oriented priority queue implemented with a binary heap
    使用数组二叉树实现大顶堆
    """
    def __init__(self, contens=()):
        """Create max-oriented priority queue"""
        self._data = [self._Item(k, v) for k, v in contens]
        if len(self) > 1:
            self._heapify()

    def __len__(self):
        return len(self._data)

    def __str__(self):
        ret = ""
        for i, item in enumerate(self._data):
            ret += str(item._key)
            if i == 2**int(math.log(i+1, 2) + 1) -2 or i == len(self._data) - 1:
                ret += '\n'
            else:
                ret += ', '
        return ret

    def _heapify(self):
        """
        从底向上堆化
        :return:
        """
        start = self._parent(len(self) - 1)
        for j in range(start, -1, -1):
            self._downheap(j)

    def _parent(self, j):
        return (j - 1) // 2

    def _left(self, j):
        return 2 * j + 1

    def _right(self, j):
        return 2 * j + 2

    def _has_right(self, j):
        return self._right(j) < len(self._data)

    def _has_left(self, j):
        return self._left(j) < len(self._data)

    def swap(self, i, j):
        """swap the element i and element j"""
        self._data[i], self._data[j] = self._data[j], self._data[i]

    def _downheap(self, j):
        """
        大顶堆的向下冒泡
        :param j:
        :return:
        """
        if self._has_left(j):
            left = self._left(j)
            max_child = left
            if self._has_right(j):
                right = self._right(j)
                if self._data[right] > self._data[left]:
                    max_child = right
            if self._data[max_child] > self._data[j]:
                self.swap(j, max_child)
                self._downheap(max_child)

    def _upheap(self, j):
        """
        向上冒泡
        :param j:
        :return:
        """
        parent = self._parent(j)
        if parent > 0 and self._data[j] > self._data[parent]:
            self.swap(j, parent)
            return self._upheap(parent)

    def max(self):
        """Return but not remove maxmum key-value"""
        if self.is_empty():
            raise Exception("maxheap priority queue is empty")
        max_item = self._data[0]
        return (max_item._key, max_item._value)

    def sort(self):
        if self.is_empty():
            raise Exception("maxheap priority queue is empty")
        for i in range(len(self)-1, -1, -1):
            # 将最大元素移动到数组尾部
            largest = self._data[0]
            self._data[0] = self._data[i]
            self._data[i] = largest
            self.max_heapify(self._data[:i], 0) # 从数组头部到位置i执行向下堆化

    def max_heapify(self, data, j):
        left = 2*j + 1
        right = 2*j + 2
        cur_len = len(data)
        if left < cur_len:
            max_child = left
            if right < cur_len:
                if self._data[right] > self._data[left]:
                    max_child = right
            if self._data[max_child] > self._data[j]:
                temp = self._data[max_child]
                self._data[max_child] = self._data[j]
                self._data[j] = temp
                self.max_heapify(data, max_child)


